#include <iostream>
#include <vector>

using namespace std;

class HashTableOpenAddressing {
private:
    vector<int> table;
    int capacity;
    int size;

public:
    HashTableOpenAddressing(int capacity) : capacity(capacity), size(0) {
        table.resize(capacity, -1);  // 初始化哈希表，-1表示空槽位
    }

    int hashFunction(int key) {
        return key % capacity;  // 使用取余操作作为哈希函数
    }

    void insert(int key) {
        if (size == capacity) {
            cout << "哈希表已满，无法插入新元素。" << endl;
            return;
        }

        int index = hashFunction(key);
        while (table[index] != -1) {  // 发生冲突时，使用线性探测法找到下一个可用的槽位
            index = (index + 1) % capacity;
        }

        table[index] = key;
        size++;
    }

    bool search(int key) {
        int index = hashFunction(key);
        int count = 0;

        while (table[index] != -1 && count < capacity) {  // 在哈希表中查找元素
            if (table[index] == key) {
                return true;
            }
            index = (index + 1) % capacity;
            count++;
        }

        return false;
    }
};

int main() {
    HashTableOpenAddressing hashTable(10);

    hashTable.insert(5);
    hashTable.insert(15);
    hashTable.insert(25);

    cout << "Search 15: " << (hashTable.search(15) ? "Found" : "Not Found") << endl;
    cout << "Search 10: " << (hashTable.search(10) ? "Found" : "Not Found") << endl;

    return 0;
}